package me.renyaoxiang.algorithm.sortforstats;

import java.util.ArrayList;
import java.util.List;

public class HeapSortForStats {
    List<Integer> dataList = new ArrayList<>();
    StatsContext statsContext;

    public HeapSortForStats(StatsContext statsContext) {
        this.statsContext = statsContext;
    }

    public static void sort(StatsContext statsContext, int[] data) {
        HeapSortForStats heapSort = new HeapSortForStats(statsContext);
        statsContext.callIndexSign();
        for (int i = 0; i < data.length; i++) {
            statsContext.callIndexCompare();
            statsContext.callIndexSign();

            heapSort.push(data[i]);
        }

        statsContext.callIndexSign();
        for (int i = 0; i < data.length; i++) {
            statsContext.callIndexCompare();
            statsContext.callIndexSign();

            statsContext.callSign();
            data[i] = heapSort.pop();
        }
    }

    private int pop() {
        statsContext.callSwap();
        swap(dataList, 0, dataList.size() - 1);

        statsContext.callSign();
        int minData = dataList.remove(dataList.size() - 1);

        statsContext.callIndexSign();
        int current = 0;

        statsContext.callIndexCompare();
        while (2 * current + 1 < dataList.size()) {
            statsContext.callIndexSign();
            int left = 2 * current + 1;
            statsContext.callIndexSign();
            int right = left + 1;
            statsContext.callIndexSign();
            int minIndex = left;
            statsContext.callCompare();
            if (hasData(right) && dataList.get(left) > dataList.get(right)) {
                statsContext.callIndexSign();
                minIndex = right;
            }
            statsContext.callCompare();
            if (dataList.get(current) > dataList.get(minIndex)) {

                statsContext.callSwap();
                swap(dataList, minIndex, current);

                statsContext.callSign();
                current = minIndex;
            } else {
                break;
            }
        }
        return minData;
    }

    private boolean hasData(int index) {
        statsContext.callIndexCompare();
        return index < dataList.size();
    }

    private void push(int it) {
        dataList.add(it);
        statsContext.callIndexSign();
        int current = dataList.size() - 1;
        statsContext.callIndexSign();
        int parent = (current - 1) / 2;
        statsContext.callIndexSign();
        statsContext.callCompare();
        while (current != parent && dataList.get(current) < dataList.get(parent)) {
            statsContext.callSwap();
            swap(dataList, current, parent);
            statsContext.callIndexSign();
            current = parent;
            statsContext.callIndexSign();
            parent = (current - 1) / 2;
        }
    }

    private void swap(List<Integer> dataList, int first, int second) {
        statsContext.callSwap();
        int temp = dataList.get(first);
        dataList.set(first, dataList.get(second));
        dataList.set(second, temp);
    }
}
